\bigskip
\bigskip
{\magonebf 5.7 Node and edge arrays (node\_array, edge\_array)}

{\bf 1. Definition}

An instance $A$ of the parameterized data type $node\_array\<E\>$ 
($edge\_array\<E\>$) is a partial mapping from the node set (edge set) 
of a (u)graph $G$ to the set of variables of data type $E$, called the 
element type of the array. The domain $I$ of $A$ is called the index set 
of $A$ and $A(x)$ is called the element at position $x$. $A$ is said to 
be valid for all nodes (edges) in $I$. 

\def\name {$node/edge\_array\<E\>$}
\def\type {$node/edge\_array$}

\bigskip
{\bf 2. Creation}

a) \create A {}

b) \create A (graph\ G)

c) \create A (graph\ G,\ E\ x)

d) \create A (graph\ G,\ int\ n,\ E\ x)    


creates an instance $A$ of type $node\_array(E)$ or $edge\_array(E)$. Variant a)
initializes the index set of $A$ to the empty set, Variants b) and c) 
initialize the index set of $A$ to be the entire node (edge) set of graph $G$,
i.e., $A$ is made valid for all nodes (edges) currently contained in $G$. 
Variant c) in addition initializes $A(i)$ with $x$ for all nodes (edges) 
$i$ of $G$. Variant d) makes $A$ a $node/edge\_array(E)$ valid for up to $n$ 
nodes/edges of $G$, \precond $n \ge |V|$ ($|E|$), this is useful if you want
to use the array for later inserted nodes/edges.



\bigskip
\def\var{$A$}
{\bf 3. Operations}
\medskip

\+\op void  init {graph\ G}         
                             {sets the index set $I$ of $A$ to the node (edge)}
\+\nop                       {set of $G$, i.e., makes $A$ valid for all nodes}
\+\nop                       {(edges) of $G$.}
\smallskip
\+\op void  init {graph\ G,\ E\ x}    
                             {makes $A$ valid for all nodes (edges) of $G$ }
\+\nop                       {and sets $A(i) = x$ for all nodes (edges) of $G$}
\smallskip
\+\op void  init {graph\ G,\ int\ n,\ E\ x}  {}
\+\nop                       {makes $A$ valid for at most $n$ nodes (edges)}
\+\nop                       {of $G$ and sets $A(i) = x$ for all nodes (edges)}
\+\nop                       {of $G$. \precond $n \ge |V|$ ($n \ge |E|$). }
\smallskip
\+\opa E\&  {node/edge\ i}                    
                             {access the variable $A(i)$.}
\+\nop                       {\precond $A$ must be valid for $i$.}

\bigskip
{\bf 4. Implementation}

Node (edge) arrays for a graph $G$ are implemented by \CC vectors and an 
internal numbering of the nodes and edges of $G$. The access operation 
takes constant time, $init$ takes time $O(n)$, where $n$ is the number of 
nodes (edges) currently in $G$. The space requirement is $O(n)$.

{\bf Remark}: A node (edge) array is only valid for a bounded number of
the nodes (edges) contained in $G$. This number is either the total number
of nodes of $G$ at the moment of the array creation (variants a) \dots c)) or 
it is explicitely set by the user (variant d)).  Access operations for 
additional later added nodes (edges) are not allowed. Fully dynamic node and
edge arrays can be realized by using hashing arrays, e.g., 
$h\_array(node,\dots)$ (cf.~section~4.5).

\vfill\eject

